Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Intersection of Two Arrays

Problem Statement

Given two arrays, nums1 and nums2 containing integers, return an array of the intersection of nums1 and nums2. In the resultant array, each integer should be unique, and elements can be in any order.

Examples

  • Example 1:

    • Input: nums1 = [3,1,2,6,7,8], nums2 = [2,3,4,5,7,9]
    • Expected Output: [2,3,7]
    • Justification: The numbers 2, 3, and 7 are present in both nums1 and nums2.
  • Example 2:

    • Input: nums1 = [1,2,3], nums2 = [4,5,6]
    • Expected Output: []
    • Justification: There are no common elements between nums1 and nums2, hence the output is an empty array.
  • Example 3:

    • Input: nums1 = [7,8,9,10], nums2 = [10,9,8,7]
    • Expected Output: [7,8,9,10]
    • Justification: All elements from nums1 are present in nums2 and vice versa.

Solution

To solve this problem, we will utilize a set-based approach. Sets are ideal for this task because they automatically remove duplicate elements and allow for efficient element lookup. First, we'll convert both input arrays into sets. This conversion eliminates any duplicates within each array, aligning with our requirement to return only unique common elements. Then, we'll find the intersection of these two sets, which gives us the set of elements present in both arrays. This method is effective because set operations are generally more efficient than iterating through arrays, especially when dealing with duplicates and the need for uniqueness. Our approach reduces the problem to simple set operations, making the solution more elegant and performant.

The rationale behind using sets over other data structures is twofold. Firstly, the automatic removal of duplicates simplifies our task. Secondly, the intersection operation directly corresponds to our goal of finding common elements, ensuring that the algorithm is both intuitive and efficient.

Step-by-step Algorithm

  1. Initialize Two Sets: Start by creating two empty sets, set1 and set2. These will store the unique elements from nums1 and nums2, respectively.
  2. Populate the First Set (set1): Loop through each element in nums1. For every element, add it to set1. This step ensures that set1 contains all unique elements from nums1.
  3. Populate the Second Set (set2): Repeat the process for nums2, adding each of its elements to set2. Now, set2 contains all unique elements from nums2.
  4. Find Intersection: Identify the common elements between set1 and set2. This can be done by checking each element of set1 to see if it also exists in set2, or by utilizing set intersection operations available in many programming languages.
  5. Prepare the Result: Convert the intersection set into an array. This step involves initializing an array and populating it with the elements from the intersection set.
  6. Return the Result: Finally, return the array created in the previous step. This array contains all unique elements that are present in both nums1 and nums2.

Algorithm Walkthrough with Input

Given nums1 = [3,1,2,6,7,8], nums2 = [2,3,4,5,7,9]:

  1. Initialize Sets:

    • set1 = {}
    • set2 = {}
  2. Populate set1:

    • Loop through nums1: add 3, 1, 2, 6, 7, and 8 to set1.
    • After the loop, set1 = {1, 2, 3, 6, 7, 8}.
  3. Populate set2:

    • Loop through nums2: add 2, 3, 4, 5, 7, and 9 to set2.
    • After the loop, set2 = {2, 3, 4, 5, 7, 9}.
  4. Find Intersection:

    • Identify common elements between set1 and set2.
    • Intersection: {2, 3, 7}.
  5. Prepare the Result:

    • Convert the intersection set to an array: [2, 3, 7].
  6. Return the Result:

    • The final result is [2, 3, 7], which is the array of unique elements present in both nums1 and nums2.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity:

  • Creating Sets: for the first array and for the second, where n and m are the lengths of the two input arrays.
  • Finding Intersection: Iterating through the smaller set and checking for each element in the larger set, leading to in the best case and in the worst case.

Thus, the overall time complexity combines these steps, resulting in .

Space Complexity:

  • Space is required for storing elements of both arrays in sets, leading to a space complexity of in the worst case when all elements are unique.
Intersection of Two Arrays (easy)
Find the Index of the First Occurrence in a String (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough with Input

Code

Complexity Analysis

Time Complexity:

Space Complexity: